The present invention relates to an image search apparatus and method for searching for a desired image (image data), and a computer readable storage medium.
Conventionally, various techniques for searching for image data of similar images (to be simply referred to as images hereinafter) have been proposed. Especially for a texture image, a scheme that uses Fourier transformation in extraction of features of the texture image is known (R. Bajcsy, xe2x80x9cComputer description of Textured Surfacesxe2x80x9d, Proc. 3rd Int. Conf. on Artificial Intelligence, pp. 572-579, 1973), and an image search apparatus that uses this scheme can be proposed.
The feature extraction method of a texture image using Fourier transformation will be briefly explained below. In this scheme, the two-dimensional Fourier transform of an input image f(x, y) is computed by:                               F          ⁡                      (                          i              ,              j                        )                          =                              ∑                          x              =              1                        n                    ⁢                      xe2x80x83                    ⁢                                    ∑                              y                =                1                            n                        ⁢                          xe2x80x83                        ⁢                                          f                ⁡                                  (                                      x                    ,                    y                                    )                                            ⁢                              ⅇ                                                      -                    2                                    ⁢                                      xe2x80x83                                    ⁢                  π                  ⁢                                                            -                      1                                                        ⁢                                                            (                                                                        ⅈ                          ⁢                                                      xe2x80x83                                                    ⁢                          x                                                +                                                  j                          ⁢                                                      xe2x80x83                                                    ⁢                          y                                                                    )                                        /                    n                                                                                                          (        1        )            
and, a power spectrum p that indicates the magnitude of the frequency component of the image f is computed by:
p(i, j)=|F(i, j)|2xe2x80x83xe2x80x83(2)
(where i and j are natural numbers (the same applies to the following description))
At this time, the power spectrum p which indicates the magnitude of the frequency component of the image f and is computed by equation (2) is adjusted so that zero frequency matches the center of spectrum, by replacing the first and third quadrants, and the second and fourth quadrants in the four quadrants of the two-dimensional coordinate system which includes the image f(x, y), and is defined by orthogonal X- and Y-axes.
When the power spectrum pxe2x80x2 that has been adjusted as described above undergoes polar coordinate conversion, a sum total p(r) of components the frequency of which is r, and a sum total p(xcex8) of frequency components in the xcex8 direction are respectively computed by:                                           p            ⁡                          (              r              )                                =                                    ∑                              i                =                0                                            n                -                1                                      ⁢                          xe2x80x83                        ⁢                                          ∑                                  j                  =                  0                                                  n                  -                  1                                            ⁢                              xe2x80x83                            ⁢                              p                ⁡                                  (                                      i                    ,                    j                                    )                                                                    ,                  xe2x80x83                ⁢                                            i              2                        +                          j              2                                =                      r            2                                              (        3        )                                                      p            ⁡                          (              θ              )                                =                                    ∑                              i                =                0                                            n                -                1                                      ⁢                          xe2x80x83                        ⁢                                          ∑                                  j                  =                  0                                                  n                  -                  1                                            ⁢                              xe2x80x83                            ⁢                              p                ⁡                                  (                                      i                    ,                    j                                    )                                                                    ,                  xe2x80x83                ⁢                                            tan                              -                1                                      ⁡                          (                              j                /                i                            )                                =          θ                                    (        4        )            
(where r is the distance from the origin, and xcex8 is the angle the polar axis of the polar coordinate system makes with r (the same applies to the following description))
According to the distribution of p(xcex8) computed by equations (4), the directionality of texture of the image f(x, y) can be determined. This directionality recognition exploits the fact that if the input image has directionality xcex8, a peak appears on the power spectrum at the angle xcex8.
The number of peaks included in this power spectrum and their magnitudes are detected, and as a result of detection, if the number of peaks is 1, xe2x80x9cunidirectionalityxe2x80x9d is determined, if the number of peaks is 2, xe2x80x9cbidirectionalityxe2x80x9d is determined, and if three or more peaks are included, xe2x80x9cno directionalityxe2x80x9d is determined.
However, upon applying the aforementioned feature extraction method to image search, the following problems remain unsolved.
(1) Directionality determination based on peak detection cannot be done unless the sum total for the entire space of the power spectrum p is computed, as indicated by equations (4). For this reason, the time required for automatic computations using an apparatus such as a computer is problematic, and an apparatus having high computation processing capability to some extent must be adopted, resulting in high total cost.
(2) When similarity between two input images is determined by comparing the directionalities of the two images, a method of normalizing the distributions of power spectra of the two images, and comparing the power spectra of the two images after normalization may be normally used. In this case, the same problem as in (1) is posed, resulting in poor practicality.
(3) Even when an input image has three or more directionalities in practice as a result of determining its directionality, xe2x80x9cno directionalityxe2x80x9d is determined, as described above.
The present invention has been made in consideration of the aforementioned problems, and has as its object to provide an image search apparatus and method, which accurately search for an image with high precision within a practical required time, and a computer readable storage medium.
In order to achieve the above object, an image search apparatus according to the present invention is characterized by the following arrangement.
That is, an image search apparatus comprises power spectrum computation means for computing a two-dimensional power spectrum of an input image by computing a two-dimensional Fourier transform of the image, standard deviation matrix generation means for segmenting the two-dimensional power spectrum computed by the power spectrum computation means into a plurality of blocks on a two-dimensional coordinate system, computing standard deviations of power spectrum components in units of blocks, and generating a matrix of the generated standard deviations, feature amount computation means for computing sums of the standard deviations as feature amounts in units of directions by making the matrix generated by the standard deviation matrix generation means using predetermined mask patterns which are prepared in advance in units of directions of interest and correspond to a pattern of the matrix, feature determination means for determining a directionality of the image on the basis of the feature amounts computed by the feature amount computation means, storage means for classifying and storing the image and the feature amounts computed by the feature amount computation means on the basis of the directionality determination result of the feature determination means, and image search means for searching for a similar image on the basis of the feature amounts and determination result stored in the storage means.
For example, the standard deviation matrix generation means generates the matrix of the standard deviations for blocks corresponding to first and second quadrants of the two-dimensional coordinate system of the plurality of segmented blocks.
For example, the mask patterns in units of directions of interest are multi-valued masks which are weighted to have the directions of interest thereof as peaks.
For example, the image search means computes a similarity between a query image designated as a query and another image by considering, as vectors, feature amounts which are stored in the storage means in correspondence with the query image and the other image as a similar image candidate, and are computed in units of directions of interest, and computing an inner product of the vectors.
In order to achieve the above object, an image search method according to the present invention is characterized by the following arrangement.
That is, an image search method comprises the power spectrum computation step of computing a two-dimensional power spectrum of an input image by computing a two-dimensional Fourier transform of the image, the standard deviation matrix generation step of segmenting the two-dimensional power spectrum computed in the power spectrum computation step into a plurality of blocks on a two-dimensional coordinate system, computing standard deviations of power spectrum components in units of blocks, and generating a matrix of the generated standard deviations, the feature amount computation step of computing sums of the standard deviations as feature amounts in units of directions by making the matrix generated in the standard deviation matrix generation step using predetermined mask patterns which are prepared in advance in units of directions of interest and correspond to a pattern of the matrix, the feature determination step of determining a directionality of the image on the basis of the feature amounts computed in the feature amount computation step, the storage step of classifying and storing the image and the feature amounts computed by the feature amount computation step on the basis of the directionality determination result in the feature determination step, and the image search step of searching for a similar image on the basis of the feature amounts and determination result stored in the storage step.
Furthermore, a computer readable storage medium is characterized by storing a program code that implements the aforementioned image search apparatus and method using a computer.
Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.